package com.gitee.wsl.collections.trie

import com.gitee.wsl.collections.trie.analyzer.KeyAnalyzer
import com.gitee.wsl.collections.trie.analyzer.StringKeyAnalyzer

/**
 * Implements a PATRICIA Trie (Practical Algorithm to Retrieve Information
 * Coded in Alphanumeric).
 *
 *
 * A PATRICIA [org.apache.commons.collections4.Trie] is a compressed
 * [org.apache.commons.collections4.Trie]. Instead of storing
 * all data at the edges of the [org.apache.commons.collections4.Trie]
 * (and having empty internal nodes), PATRICIA stores data in every node.
 * This allows for very efficient traversal, insert, delete, predecessor,
 * successor, prefix, range, and [.select]
 * operations. All operations are performed at worst in O(K) time, where K
 * is the number of bits in the largest item in the tree. In practice,
 * operations actually take O(A(K)) time, where A(K) is the average number of
 * bits of all items in the tree.
 *
 *
 *
 * Most importantly, PATRICIA requires very few comparisons to keys while
 * doing any operation. While performing a lookup, each comparison (at most
 * K of them, described above) will perform a single bit comparison against
 * the given key, instead of comparing the entire key to another key.
 *
 *
 *
 * The [org.apache.commons.collections4.Trie] can return operations in
 * lexicographical order using the 'prefixMap', 'submap', or 'iterator' methods.
 * The [org.apache.commons.collections4.Trie] can also
 * scan for items that are 'bitwise' (using an XOR metric) by the 'select' method.
 * Bitwise closeness is determined by the [KeyAnalyzer] returning true or
 * false for a bit being set or not in a given key.
 *
 *
 *
 * This PATRICIA [org.apache.commons.collections4.Trie] supports both variable
 * length &amp; fixed length keys. Some methods, such as [org.apache.commons.collections4.Trie.prefixMap]
 * are suited only to variable length keys.
 *
 *
 * @param <V> the type of the values in this map
 * @see [Radix Tree](https://en.wikipedia.org/wiki/Radix_tree)
 *
 * @see [PATRICIA](https://users.monash.edu/~lloyd/tildeAlgDS/Tree/PATRICIA/)
 *
 * @see [Crit-Bit Tree](https://www.imperialviolet.org/binary/critbit.pdf)
 *
 * @since 4.0
</V> */
class PatriciaTrie<V> : AbstractPatriciaTrie<String, V> {
    /**
     * Constructs a new instance.
     */
    constructor() : super(StringKeyAnalyzer.INSTANCE)

    /**
     * Constructs a new instance.
     *
     * @param map mappings to be stored in this map.
     */
    constructor(map: Map<String, V>) : super(StringKeyAnalyzer.INSTANCE, map)

}
